package dp;

import java.util.Arrays;

public class D230824 {
    // 打家劫舍(一)
    // 不能偷相邻两家
    // 时间：O(N)
    // 空间：O(N)
    public int rob (int[] nums) {
        int n = nums.length;
        // dp[i] 表示长度为 i 的数组，最多能获取的多少钱
        int[] dp = new int[n + 1];
        // 初始化，长度为 1 时，只有一家的情况
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            // 对于当前 i
            // 我们可以选择偷 或者 不偷
            // 偷：那么就是不偷上一家 dp[i - 2]  + 当前这一家 nums[i - 1]
            // 不偷：就等于 dp[i - 1]
            // 选较大值即可
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }


    // 打家劫舍(二)
    // 不能偷相邻两家
    // 沿湖的房间形成一个闭环，第一家和最后一家是相邻的
    // 时间：O(N)
    // 空间：O(N)
    public int rob2 (int[] nums) {
        // dp[i] 表示长度为 i 的数组，最多能获取的多少钱
        int[] dp = new int[nums.length + 1];
        // 选择偷了第一家
        dp[1] = nums[0];
        // 最后一家不能偷（不遍历最后一家）
        for(int i = 2; i < nums.length; i++)
            //对于每家可以选择偷或者不偷
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        int res = dp[nums.length - 1];

        // 清除dp数组，第二次循环
        Arrays.fill(dp, 0);
        // 不偷第一家
        dp[1] = 0;
        // 可以偷最后一家
        for(int i = 2; i <= nums.length; i++)
            // 对于每家可以选择偷或者不偷
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        // 选择最大值
        return Math.max(res, dp[nums.length]);
    }
}
